#pragma once
#include<iostream>
#include<vector>
using namespace std;
inline unsigned long __stl_next_prime(unsigned long n)
{
	// Note: assumes long is at least 32 bits.
	static const int __stl_num_primes = 28;
	static const unsigned long __stl_prime_list[__stl_num_primes] = {
		12, 97, 193, 389, 769,
		1543, 3079, 6151, 12289, 24593,
		49157, 98317, 196613, 393241, 786433,
		1572869, 3145739, 6291469, 12582917, 25165843,
		50331653, 100663319, 201326611, 402653189, 805306457,
		1610612741, 3221225473, 4294967291
	};
	const unsigned long* first = __stl_prime_list;
	const unsigned long* last = __stl_prime_list + __stl_num_primes;
	const unsigned long* pos = lower_bound(first, last, n);
	return pos == last ? *(last - 1) : *pos;
}

//namespace openaddress
//{	
//	typedef enum state
//	{
//		EXIST,
//		EMPTY,
//		DEL
//	}state;
//
//	template<class T>
//	struct hashData
//	{
//		state _state = EMPTY;
//		T _data;
//	};
//
//	template<class K>
//	struct hashfunc
//	{
//		size_t operator()(const K& k)
//		{
//			return (size_t)k;
//		}
//	};
//
//	template<class K, class V, class HASHFUNC = hashfunc<K>,class GETVAL>
//	class hashTable
//	{
//	public:
//		hashTable()
//			:_tables(11)
//			, _size(0)
//		{}
//
//		void insert(const V& data)
//		{
//			size_t capacity = _tables.size();
//			if (_size * 10 / capacity >= 0.7)
//			{
//				hashTable<K, V, HASHFUNC,GETVAL>newTables;
//				newTables._tables.resize(2 * capacity);
//				for (auto& e : _tables)
//					if (e._state == EXIST)
//						newTables.insert(e._data);
//				std::swap(_tables, newTables._tables);
//				std::swap(_size, newTables._size);
//			}
//			size_t hash0 = func(getval(data)) % capacity;
//			size_t hashi = hash0;
//			size_t i = 1;
//			while (_tables[hashi]._state == EXIST)
//				hashi = (hashi + i++) % capacity;
//			_tables[hashi]._data = data;
//			_tables[hashi]._state = EXIST;
//			_size++;
//		}
//
//		hashData<T>* find(const K& k)
//		{
//			int sz = _tables.size();
//			size_t hash0 = func(k) % sz;
//			size_t hashi = hash0;
//			size_t i = 1;
//			while (_tables[hashi]._state != EMPTY)
//			{
//				if (_tables[hashi]._state == EXIST && getval(_tables[hashi]._data) == k)
//					return &_tables[hashi];
//				hashi = (hashi + i++) % sz;
//			}
//			return nullptr;
//		}
//
//		bool erase(const V& k)
//		{
//			auto deldata = find(getval(k));
//			if (deldata)
//			{
//				deldata->_state = DEL;
//				return true;
//			}
//			else
//				return false;
//		}
//
//		void show()
//		{
//			for (auto& e : _tables)
//				cout << getval(e._data) << ' ';
//			cout << endl;
//		}
//	private:
//		vector<hashData<T>>_tables;
//		size_t _size;
//		HASHFUNC func;
//		GETVAL getval;
//	};
//
//}
namespace hashbucket
{
	template<class V>
	struct HashNode
	{
		V _kv;
		struct HashNode<V>* _next;
		HashNode(const V& kv = { V() }, struct HashNode<V>* next = nullptr)
			:_kv(kv)
			, _next(next)
		{}
	};
	template<class K, class V, class HASH, class GETVAL>class HashTable;
	template<class K, class T,class Ptr,class Ref, class HASH, class GETVAL>
	struct Iterator
	{
		typedef Iterator<K,T,Ptr, Ref, HASH, GETVAL> Self;
		typedef HashNode<T> Node;
		typedef HashTable<K, T, HASH, GETVAL> HT;
		Node* _node;
		HASH _hash;
		GETVAL _getval;
		const HT* _ht;
		Iterator(Node* node,const HT* ht)
			:_node(node)
			,_ht(ht)
		{}

		Ptr operator->() { return &_node->_kv; }
		Ref operator*() { return _node->_kv; }
		bool operator!=(const Self& other) { return _node != other._node; }

		Self& operator++()
		{
			if (_node->_next)
				_node = _node->_next;
			else
			{
				size_t hashi = _hash(_getval(_node->_kv)) % _ht->size();
				hashi++;
				while (hashi != _ht->size())
				{
					_node = _ht->_tables[hashi];
					if (_node)
						break;
					hashi++;
				}
				if (hashi == _ht->size())
					_node = nullptr;
			}
			return *this;
		}
	};

	template<class K,class V,class HASH,class GETVAL>
	class HashTable
	{
	private:
		
	public:
		typedef struct HashNode<V> node;
		typedef Iterator<K, V, V*, V&, HASH, GETVAL> iterater;
		typedef Iterator<K, V, const V*, const V&, HASH, GETVAL> const_iterater;
		HashTable()
			:_tables(11)
			,_n(0)
		{}
		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				node* cur = _tables[i];
				_tables[i] = nullptr;
				while (cur)
				{
					node* del = cur;
					cur = cur->_next;
					delete del;
				}
			}
		}
		HashTable(const HashTable<K, V,HASH,GETVAL>& other)
			:_tables(11)
			, _n(0)
		{
			_n = other._n;
			func = other.func;
			for (size_t i = 0; i < other._tables.size();i++)
			{
				node* cur = other._tables[i];
				while (cur)
				{
					insert(cur->_kv);
					cur = cur->_next;
				}
			}
		}
		HashTable<K, V, HASH,GETVAL>& operator=(HashTable<K, V, HASH,GETVAL> other)
		{
			swap(_n, other._n);
			swap(func, other.func);
			swap(_tables, other._tables);
			swap(getkey, other.getkey);
			return *this;
		}

		iterater begin()
		{
			if (_n == 0)
				return end();
			for (auto el : _tables)
				if (!el)
					return { el,this };
		}
		iterater end() { return { nullptr,this }; }
		
		const_iterater begin()const 
		{
			if (_n == 0)
				return end();
			for (auto el : _tables)
				if (!el)
					return { el,this };
		}
		const_iterater end()const  { return { nullptr,this }; }


		pair<iterater, bool> insert(const V& kv)
		{
			size_t size = _tables.size();
			if (size == _n)
			{
				int new_n = __stl_next_prime(_n + 1);
				vector<node*>new_tables(new_n);
				for (size_t i = 0; i < _n; i++)
				{
					node* cur = _tables[i];
					while (cur)
					{
						node* next = cur->_next;
						size_t hashi = func(getkey(kv)) % new_n;
						cur->_next = new_tables[hashi];
						new_tables[hashi] = cur;
						cur = next;
					}
				}
				swap(new_tables, _tables);
			}
			size = _tables.size();
			size_t hashi = func(getkey(kv)) % size;
			node* newnode = new node(kv);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			_n++;
			return { iterater(newnode,this) , true };
		}

		iterater find(const K& k)
		{
			int size = _tables.size();
			size_t hashi = func(k) % size;
			node* cur = _tables[hashi];
			while (cur)
			{
				if (getkey(cur->_kv) == k)
					return { cur ,this};
				cur = cur->_next;
			}
			return end();
		}

		bool erase(const K& k)
		{
			int size = _tables.size();
			size_t hashi = func(k) % size;
			node* cur = _tables[hashi];
			if (cur && getkey(cur->_kv) == k)
			{
				_tables[hashi] = cur->_next;
				delete cur;
				_n--;
				return true;
			}
			else if(cur)
			{
				while (cur->_next)
				{
					if (getkey(cur->_next->_kv) == k)
					{
						node* del = cur->_next;
						cur->_next = del->_next;
						delete cur;
						_n--;
						return true;
					}
					cur = cur->_next;
				}
			}
			return false;
		}
		size_t size()const { return _n; }

	private:
		vector<node*>_tables;
		HASH func;
		size_t _n;
		GETVAL getkey;
	};
}